package 加油站;

/**
 * @author: AirMan
 * @date: 2025/4/23 10:42
 * @description:
 */
public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        // greedy
        // 为什么一旦[0，i] 区间和为负数，起始位置就可以是i+1呢，i+1后面就不会出现更大的负数？
        // 如果出现更大的负数，就是更新i，那么起始位置又变成新的i+1了。
        // 那有没有可能 [0，i] 区间 选某一个作为起点，累加到 i这里 curSum是不会小于零呢？
        // 反证法：
        // 如果 curSum<0 说明 区间和1 + 区间和2 < 0， 那么 假设从上图中的位置开始计数curSum不会小于0的话，就是 区间和2>0。
        // 区间和1 + 区间和2 < 0 同时 区间和2>0，只能说明区间和1 < 0， 那么就会从假设的箭头初就开始从新选择起始位置了。

        // 局部最优：当前累加rest[i]的和curSum一旦小于0，起始位置至少要是i+1，因为从i之前开始一定不行

        int curSum = 0;
        int toatalSum = 0;
        int start = 0;
        for (int i = 0; i < gas.length; i++) {
            int rest = gas[i] - cost[i];
            curSum += rest;
            toatalSum += rest;
            if (curSum < 0) {
                start = i + 1;
                curSum = 0;
            }
        }
        if (toatalSum < 0) {
            return -1;
        }
        return start;
    }
}
